import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

// 数据类型
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Leetcode_897 {

    /**
     *  方法一：
     *      1. 首先中序遍历，将遍历结果存到链表中
     *      2. 将链表中的数据取出，重新排成要求的树
     *  注意点：
     *      1. inorder 不需要返回值，见 inorder02() 方法
     *      2. foreach 的idea快捷方式 iter，其格式比 foreach的要好
     */
    public TreeNode increasingBST01(TreeNode root) {

        // 新建一个辅助列表
        List<Integer> list = new ArrayList<>();
        // 进行中序遍历
        inorder01(root,list);

        // 新建一个伪节点
        TreeNode dummyNode = new TreeNode(-1);
        TreeNode currNode = dummyNode;
        // 新建题目要求的树（快捷键 iter）
        for (Integer integer : list) {
            currNode.right = new TreeNode(integer);
            currNode = currNode.right;
        }

        // 返回 伪节点的右子树，这才是真正新建的树
        return dummyNode.right;
    }

    // 中序遍历（递归）（应该不需要返回值）
    private List<Integer> inorder01(TreeNode treeNode , List<Integer> list){
        // 判空（即使用例不空，递归到叶子节点时，也会有null）
        if (treeNode == null){
            return null;
        }
        // 中序
        inorder01(treeNode.left,list);
        list.add(treeNode.val);
        inorder01(treeNode.right,list);
        return list;
    }


    /**
     *  方法二：
     *      1. 一边 中序遍历，一边 修改结构
     */
    // 类似于辅助指针，存放修改后的 树的 最新确定节点
    private TreeNode tempNode;

    public TreeNode increasingBST2(TreeNode root){
        TreeNode dummyNode = new TreeNode(-1);
        tempNode = dummyNode;
        inorder02(root);
        return dummyNode.right;
    }

    // 中序遍历
    private void inorder02(TreeNode treeNode){
        // 判空（即使用例不空，递归到叶子节点时，也会有null）
        if (treeNode == null){
            // void 返回类型 的 return
            return;
        }

        // 中序
        inorder02(treeNode.left);

        // 具体节点的操作
        // 找到节点，先把它加入到 新建的树之中（修改之后的树）
        tempNode.right = treeNode;
        // 之后，把新加入的节点，修改的 符合新树的要求
        treeNode.left = null;
        // treeNode.right 在上一步的 tempNode.right = treeNode; 中实现（下一个节点确定之后）
        // 所以，要使 tempNode = treeNode;
        tempNode = treeNode;

        inorder02(treeNode.right);
    }
}
